home *** CD-ROM | disk | FTP | other *** search
/ PD Collection CD 1 / PD Collection CD 1.iso / textual / tex / files / !tex / TeXsource / commontex / c / par < prev    next >
Encoding:
Text File  |  1988-04-18  |  47.5 KB  |  1,097 lines
  1. /*
  2.  *    Copyright 1986, 1987 Pat Joseph Monardo. All rights reserved.
  3.  *    Copying of this file is granted according to the provisions 
  4.  *    specified in the file COPYING which must accompany this file.
  5.  */
  6.  
  7.  
  8. /*
  9.  *              par.c
  10.  */
  11.  
  12. #include "tex.h"
  13. #include "heap.h"
  14. #include "arith.h"
  15. #include "eq.h"
  16. #include "tfm.h"
  17. #include "str.h"
  18. #include "tokenstack.h"
  19. #include "evalstack.h"
  20. #include "box.h"
  21. #include "pack.h"
  22. #include "hyph.h"
  23. #include "print.h"
  24. #include "error.h"
  25. #include "par.h"
  26.  
  27. scal    active_width[7];
  28. val             actual_looseness;
  29. scal    background[7];
  30. ptr             best_bet;
  31. hword   best_line;
  32. hword   best_pl_line[4];
  33. ptr             best_place[4];
  34. scal    break_width[7];
  35. scal    cur_active_width[7];
  36. ptr             cur_p;
  37. scal    disc_width;
  38. hword   easy_line;
  39. val             fewest_demerits;
  40. scal    first_indent;
  41. scal    first_width;
  42. ptr             just_box;
  43. hword   last_special_line;
  44. int             line_diff;
  45. val             minimal_demerits[4];
  46. val             minimum_demerits;
  47. bool    no_shrink_error_yet;
  48. ptr             passive;
  49. ptr             printed_node;
  50. hword            pass_number;
  51. scal    second_indent;
  52. bool    second_pass;
  53. scal    second_width;
  54. val             threshold;
  55.  
  56. #define act_width       active_width[1]
  57.  
  58. #define store_background(W) \
  59.         (active_width[W] = background[W])
  60.  
  61. #define store_break_width(W) \
  62.         (active_width[W] = break_width[W])
  63.  
  64. #define update_active(W) \
  65.         (active_width[W] += mem[r + W].sc)
  66.  
  67. #define copy_to_cur_active(W) \
  68.         (cur_active_width[W] = active_width[W])
  69.  
  70. #define downdate_width(W) \
  71.         (cur_active_width[W] -= mem[prev_r + W].sc)
  72.  
  73. #define update_width(W) \
  74.         (cur_active_width[W] += mem[r + W].sc)
  75.  
  76. #define set_break_width_to_background(W) \
  77.         (break_width[W] = background[W])
  78.  
  79. #define combine_two_deltas(W) \
  80.         (mem[prev_r + W].sc += mem[r + W].sc)
  81.  
  82. #define convert_to_break_width(W) \
  83.         (mem[prev_r + W].sc = mem[prev_r + W].sc + \
  84.                                                         break_width[W] - cur_active_width[W])
  85.  
  86. #define new_delta_to_break_width(W) \
  87.         (mem[q + W].sc = break_width[W] - cur_active_width[W])
  88.  
  89. #define new_delta_from_break_width(W) \
  90.         (mem[q + W].sc = cur_active_width[W] - break_width[W])
  91.  
  92. #define width_lig_char(C) \
  93.         char_width(font(lig_char(C)), \
  94.                                 char_info(font(lig_char(C)), character(lig_char(C))))
  95.  
  96. #define width_char(C) \
  97.         char_width(font(C), char_info(font(C), character(C)))
  98.                 
  99. #ifdef STAT
  100. show_break_node (q, f, h)
  101.         ptr             q;
  102.         int             f;
  103.         int             h;
  104. {
  105.         if (tracing_paragraphs > 0) {
  106.                 print_nl("@@");
  107.                 print_int(serial(passive));
  108.                 print(": line ");
  109.                 print_int(line_number(q) - 1);
  110.                 print_char('.');
  111.                 print_int(f);
  112.                 if (h == HYPHENATED)
  113.                         print_char('-');
  114.                 print(" t=");
  115.                 print_val(total_demerits(q));
  116.                 print(" -> @@");
  117.                 if (prev_break(passive) == NULL)
  118.                         print("0");
  119.                 else print_int(serial(prev_break(passive)));
  120.         }
  121. }
  122.  
  123. show_break_status (r, a, b, p, d)
  124.         ptr             r;
  125.         bool    a;
  126.         val             b;
  127.         val             p;
  128.         val             d;
  129. {
  130.         ptr             save_link;
  131.  
  132.         if (tracing_paragraphs > 0) {
  133.                 if (printed_node != cur_p) {
  134.                         print_nl("");
  135.                         if (cur_p == NULL)
  136.                                 short_display(link(printed_node));
  137.                         else {
  138.                                 save_link = link(cur_p);
  139.                                 link(cur_p) = NULL;
  140.                                 print_nl("");
  141.                                 short_display(link(printed_node));
  142.                                 link(cur_p) = save_link;
  143.                         }
  144.                         printed_node = cur_p;
  145.                 }
  146.                 print_nl("@");
  147.                 if (cur_p == NULL)
  148.                         print_esc("par");
  149.                 else if (type(cur_p) != GLUE_NODE) {
  150.                         if (type(cur_p) == PENALTY_NODE)
  151.                                 print_esc("penalty");
  152.                         else if (type(cur_p) == DISC_NODE)
  153.                                 print_esc("discretionary");
  154.                         else if (type(cur_p) == KERN_NODE)
  155.                                 print_esc("kern");
  156.                         else print_esc("math");
  157.                 }
  158.                 print(" via @@");
  159.                 if (break_node(r) == NULL)
  160.                         print_char('0');
  161.                 else print_int(serial(break_node(r)));
  162.                 print(" b=");
  163.                 if (a) print_char('*');
  164.                 else print_val(b);
  165.                 print(" p=");
  166.                 print_val(p);
  167.                 print(" d=");
  168.                 print_val(d);
  169.         }
  170. }
  171.  
  172. update_printed_node()
  173. {
  174.         int     t;
  175.  
  176.         if (cur_p == printed_node &&
  177.                 cur_p != NULL &&
  178.                 type(cur_p) == DISC_NODE)
  179.                 for (t = replace_count(cur_p); t > 0; decr(t))
  180.                         printed_node = link(printed_node);
  181. }
  182. #endif
  183.  
  184. set_break_width (break_type)
  185.         int             break_type;
  186. {
  187.         ptr             s;
  188.         int     t;/*DIFF*/
  189.         ptr             v;
  190.  
  191.         do_all_six(set_break_width_to_background);
  192.         s = cur_p;/*DIFF*/
  193.         if (break_type > UNHYPHENATED && cur_p == NULL) {/*DIFF*/
  194.                 t = replace_count(cur_p);
  195.                 v = cur_p; s = post_break(cur_p);/*DIFF*/
  196.                 while (t > 0) {
  197.                         decr(t);
  198.                         v = link(v);
  199.                         if (is_char_node(v))
  200.                                 break_width[1] -= width_char(v);
  201.                         else {
  202.                                 switch (type(v))/*DIFF*/
  203.                                 {
  204.                                 case LIGATURE_NODE:
  205.                                         break_width[1] -= width_lig_char(v);/*DIFF*/
  206.                                         break;
  207.  
  208.                                 case HLIST_NODE:
  209.                                 case VLIST_NODE:
  210.                                 case RULE_NODE:
  211.                                 case KERN_NODE:
  212.                                         break_width[1] -= width(v);/*DIFF*/
  213.                                         break;
  214.  
  215.                                 default:
  216.                                         confusion("disc1");
  217.                                         break;
  218.                                 }
  219.                         }
  220.                 }
  221.                 for ( ; s != NULL; s = link(s)) {/*DIFF*/
  222.                         if (is_char_node(s))
  223.                                 break_width[1] += width_char(s);
  224.                         else {
  225.                                 switch (type(s))
  226.                                 {
  227.                                 case LIGATURE_NODE:
  228.                                         break_width[1] += width_lig_char(s);
  229.                                         break;
  230.  
  231.                                 case HLIST_NODE:
  232.                                 case VLIST_NODE:
  233.                                 case RULE_NODE:
  234.                                 /*DIFF case KERN_NODE:*/
  235.                                         break_width[1] += width(s);
  236.                                         break;
  237.  
  238.                                 case KERN_NODE:/*DIFF*/
  239.                                         if (t == 0 && subtype(s) != ACC_KERN)/*DIFF*/
  240.                                             t = -1;/*DIFF*/
  241.                                         else/*DIFF*/
  242.                                             break_width[1] += width(s);/*DIFF*/
  243.                                         break;/*DIFF*/
  244.   
  245.                                 default:
  246.                                         confusion("disc2");
  247.                                         break;
  248.                                 }
  249.                         }
  250.                         incr(t);/*DIFF*/
  251.                 }
  252.                 break_width[1] += disc_width;
  253.                 if (t == 0) s = link(v);/*DIFF*/
  254.         }
  255.         for ( ; s != NULL; s = link(s)) {/*DIFF*/
  256.                 if (is_char_node(s))
  257.                         return;
  258.                 switch (type(s))
  259.                 {
  260.                 case GLUE_NODE:
  261.                         v = glue_ptr(s);
  262.                         break_width[1] -= width(v);
  263.                         break_width[2 + stretch_order(v)] -= stretch(v);
  264.                         break_width[6] -= shrink(v);
  265.                         break;
  266.   
  267.                 case PENALTY_NODE:
  268.                         break;
  269.              
  270.                 case MATH_NODE:
  271.                 case KERN_NODE:
  272.                         if (subtype(s) == ACC_KERN) 
  273.                                 return;
  274.                         else break_width[1] -= width(s);
  275.                         break;
  276.       
  277.                 default:
  278.                         return;
  279.                         break;
  280.                 }
  281.         }/*DIFF*/
  282. }
  283.  
  284. try_break (pi, break_type)
  285.         val             pi;
  286.         int             break_type;
  287. {
  288.         val             b;
  289.         val             d;
  290.         hword   l;
  291.         ptr             q;
  292.         ptr             r;
  293.         hword   old_l;
  294.         ptr             prev_r;
  295.         int             fit_class;
  296.         scal    shortfall;
  297.         scal    line_width;
  298.         ptr             prev_prev_r;
  299.         bool    no_break_yet;
  300.         bool    artificial_badness;
  301.         bool    node_r_stays_active;
  302.         
  303.         no_break_yet = TRUE;
  304.         old_l = 0;
  305.         prev_r = active;
  306.         if (abs(pi) >= INF_PENALTY) {
  307.                 if (pi > 0) {
  308. #ifdef STAT
  309.                         update_printed_node();
  310. #endif
  311.                         return;
  312.                 } else
  313.                         pi = EJECT_PENALTY;
  314.         }
  315.         do_all_six(copy_to_cur_active);
  316.         loop {
  317.                 r = link(prev_r);
  318.                 if (type(r) == DELTA_NODE) {
  319.                         do_all_six(update_width);
  320.                         prev_prev_r = prev_r;
  321.                         prev_r = r;
  322.                         continue;
  323.                 }
  324.                 l = line_number(r);
  325.                 if (l > old_l) {
  326.                         if (minimum_demerits < AWFUL_BAD &&
  327.                                 (old_l != easy_line || r == last_active)) {
  328.                                 if (no_break_yet) {
  329.                                         no_break_yet = FALSE;
  330.                                         set_break_width(break_type);
  331.                                 }
  332.                                 if (type(prev_r) == DELTA_NODE) {
  333.                                         do_all_six(convert_to_break_width);
  334.                                 } else if (prev_r == active) {
  335.                                         do_all_six(store_break_width);
  336.                                 } else {
  337.                                         q = get_node(DELTA_NODE_SIZE);
  338.                                         link(q) = r;
  339.                                         type(q) = DELTA_NODE;
  340.                                         subtype(q) = 0;
  341.                                         do_all_six(new_delta_to_break_width);
  342.                                         link(prev_r) = q;
  343.                                         prev_prev_r = prev_r;
  344.                                         prev_r = q;
  345.                                 }
  346.                                 minimum_demerits += abs(adj_demerits);
  347.                                 fit_class = VERY_LOOSE_FIT;
  348.                                 while (fit_class <= TIGHT_FIT) {
  349.                                         if (minimal_demerits[fit_class] <= minimum_demerits) {
  350.                                                 q = get_node(PASSIVE_NODE_SIZE);
  351.                                                 link(q) = passive;
  352.                                                 passive = q;
  353.                                                 cur_break(q) = cur_p;
  354. #ifdef STAT
  355.                                                 incr(pass_number);
  356.                                                 serial(q) = pass_number;
  357. #endif
  358.                                                 prev_break(q) = best_place[fit_class];
  359.                                                 q = get_node(ACTIVE_NODE_SIZE);
  360.                                                 break_node(q) = passive;
  361.                                                 line_number(q) = best_pl_line[fit_class] + 1;
  362.                                                 fitness(q) = fit_class;
  363.                                                 type(q) = break_type;
  364.                                                 total_demerits(q) = minimal_demerits[fit_class];
  365.                                                 link(q) = r;
  366.                                                 link(prev_r) = q;
  367.                                                 prev_r = q;
  368. #ifdef STAT
  369.                                                 show_break_node(q, fit_class, break_type);
  370. #endif
  371.                                         }
  372.                                         minimal_demerits[fit_class] = AWFUL_BAD;
  373.                                         incr(fit_class);
  374.                                 }
  375.                                 minimum_demerits = AWFUL_BAD;
  376.                                 if (r != last_active) {
  377.                                         q = get_node(DELTA_NODE_SIZE);
  378.                                         link(q) = r;
  379.                                         type(q) = DELTA_NODE;
  380.                                         subtype(q) = 0;
  381.                                         do_all_six(new_delta_from_break_width);
  382.                                         link(prev_r) = q;
  383.                                         prev_prev_r = prev_r;
  384.                                         prev_r = q;
  385.                                 }
  386.                         }
  387.                         if (r == last_active) {
  388. #ifdef STAT
  389.                                 update_printed_node();
  390. #endif
  391.                                 return;
  392.                         }
  393.                         if (l > easy_line) {
  394.                                 line_width = second_width;
  395.                                 old_l = MAX_HALFWORD - 1;
  396.                         } else {
  397.                                 old_l = l;
  398.                                 if (l > last_special_line)
  399.                                         line_width = second_width;
  400.                                 else if (par_shape_ptr == NULL)
  401.                                         line_width = first_width;
  402.                                 else line_width = mem[par_shape_ptr + 2 * l].sc;
  403.                         }
  404.                 }
  405. #ifdef STAT
  406.                 artificial_badness = FALSE;
  407. #endif
  408.                 shortfall = line_width - cur_active_width[1];
  409.                 if (shortfall > 0) {
  410.                         if (cur_active_width[3] != 0 ||
  411.                                 cur_active_width[4] != 0 ||
  412.                                 cur_active_width[5] != 0) {
  413.                                 b = 0;
  414.                                 fit_class = DECENT_FIT;
  415.                         } else {
  416.                                 if (shortfall > 7230584 && cur_active_width[2] < 1663497) {
  417.                                         b = INF_BAD;
  418.                                         fit_class = VERY_LOOSE_FIT;
  419.                                         goto done;
  420.                                 }
  421.                                 b = badness(shortfall, cur_active_width[2]);
  422.                                 if (b > 12)
  423.                                         if (b > 99)
  424.                                                 fit_class = VERY_LOOSE_FIT;
  425.                                         else fit_class = LOOSE_FIT;
  426.                                 else fit_class = DECENT_FIT;
  427.                         }
  428.                 } else {
  429.                         if (-shortfall > cur_active_width[6])
  430.                                 b = INF_BAD + 1;
  431.                         else b = badness(-shortfall, cur_active_width[6]);
  432.                         if (b > 12)
  433.                                 fit_class = TIGHT_FIT;
  434.                         else fit_class = DECENT_FIT;
  435.                 }
  436.                 
  437.         done:
  438.                 if (b > INF_BAD || pi == EJECT_PENALTY) {
  439.                         if (second_pass &&
  440.                                 minimum_demerits == AWFUL_BAD &&
  441.                                 link(r) == last_active &&
  442.                                 prev_r == active) {
  443.                                 b = 0;
  444. #ifdef STAT
  445.                                 artificial_badness = TRUE;
  446. #endif
  447.                         } else if (b > threshold)
  448.                                 goto deactivate;
  449.                         node_r_stays_active = FALSE;
  450.                 } else {
  451.                         prev_r = r;
  452.                         if (b > threshold) continue;
  453.                         node_r_stays_active = TRUE;
  454.                 }
  455.                 d = line_penalty + b;
  456.                 d = d * d;
  457.                 if (pi != 0) {
  458.                         if (pi > 0)
  459.                                 d += pi * pi;
  460.                         else if (pi > EJECT_PENALTY)
  461.                                 d -= pi * pi;
  462.                 }
  463.                 if (break_type == HYPHENATED && type(r) == HYPHENATED) {
  464.                         if (cur_p != NULL)
  465.                                 d += double_hyphen_demerits;
  466.                         else d += final_hyphen_demerits;
  467.                 }
  468.                 if (abs(fit_class - (int) fitness(r)) > 1)
  469.                         d += adj_demerits;
  470. #ifdef STAT
  471.                 show_break_status(r, artificial_badness, b, pi, d);
  472. #endif
  473.                 d += total_demerits(r);
  474.                 if (d <= minimal_demerits[fit_class]) {
  475.                         minimal_demerits[fit_class] = d;
  476.                         best_place[fit_class] = break_node(r);
  477.                         best_pl_line[fit_class] = l;
  478.                         if (d < minimum_demerits)
  479.                                 minimum_demerits = d;
  480.                 }
  481.                 if (node_r_stays_active) continue;
  482.                 
  483.         deactivate:
  484.                 link(prev_r) = link(r);
  485.                 free_node(r, ACTIVE_NODE_SIZE);
  486.                 if (prev_r == active) {
  487.                         r = link(active);
  488.                         if (type(r) == DELTA_NODE) {
  489.                                 do_all_six(update_active);
  490.                                 do_all_six(copy_to_cur_active);
  491.                                 link(active) = link(r);
  492.                                 free_node(r, DELTA_NODE_SIZE);
  493.                         }
  494.                 } else if (type(prev_r) == DELTA_NODE) {
  495.                         r = link(prev_r);
  496.                         if (r == last_active) {
  497.                                 do_all_six(downdate_width);
  498.                                 link(prev_prev_r) = last_active;
  499.                                 free_node(prev_r, DELTA_NODE_SIZE);
  500.                                 prev_r = prev_prev_r;
  501.                         } else if (type(r) == DELTA_NODE) {
  502.                                 do_all_six(update_width);
  503.                                 do_all_six(combine_two_deltas);
  504.                                 link(prev_r) = link(r);
  505.                                 free_node(r, DELTA_NODE_SIZE);
  506.                         }
  507.                 }
  508.         }
  509. }
  510.  
  511.  
  512. #define kern_break() \
  513.         {if (!is_char_node(link(cur_p)) && auto_breaking && \
  514.                 type(link(cur_p)) == GLUE_NODE) \
  515.                 try_break(0L, UNHYPHENATED); \
  516.         act_width += width(cur_p);}
  517.  
  518. #define check_shrinkage(S) \
  519.         {if (shrink_order(S) != NORMAL && shrink(S) != 0) \
  520.                 S = finite_shrink(S);}
  521.  
  522. line_break (final_widow_penalty)
  523.         val             final_widow_penalty;
  524. {
  525.         int             c;
  526.         int             j;
  527.         ptr             q;
  528.         ptr             r;
  529.         ptr             s;
  530.         ptr             prev_p;
  531.         bool    auto_breaking;
  532.  
  533.         pack_begin_line = mode_line;
  534.         link(temp_head) = link(head);
  535.         if (is_char_node(tail)) {
  536.                 tail_append(new_penalty(INF_PENALTY));
  537.         } else if (type(tail) != GLUE_NODE) {
  538.                 tail_append(new_penalty(INF_PENALTY));
  539.         } else {
  540.                 type(tail) = PENALTY_NODE;
  541.                 delete_glue_ref(glue_ptr(tail));
  542.                 flush_node_list(leader_ptr(tail));
  543.                 penalty(tail) = INF_PENALTY;
  544.         }
  545.         link(tail) = new_param_glue(PAR_FILL_SKIP_CODE);
  546.         pop_nest();
  547.         no_shrink_error_yet = TRUE;
  548.         check_shrinkage(left_skip);
  549.         check_shrinkage(right_skip);
  550.         q = left_skip;
  551.         r = right_skip;
  552.         background[1] = width(q) + width(r);
  553.         background[2] = 0;
  554.         background[3] = 0;
  555.         background[4] = 0;
  556.         background[5] = 0;
  557.         background[2 + stretch_order(q)] = stretch(q);
  558.         background[2 + stretch_order(r)] += stretch(r);
  559.         background[6] = shrink(q) + shrink(r);
  560.         minimum_demerits = AWFUL_BAD;
  561.         minimal_demerits[VERY_LOOSE_FIT] = AWFUL_BAD;
  562.         minimal_demerits[LOOSE_FIT] = AWFUL_BAD;
  563.         minimal_demerits[DECENT_FIT] = AWFUL_BAD;
  564.         minimal_demerits[TIGHT_FIT] = AWFUL_BAD;
  565.         if (par_shape_ptr == NULL) {
  566.                 if (hang_indent == 0) {
  567.                         last_special_line = 0;
  568.                         second_width = hsize;
  569.                         second_indent = 0;
  570.                 } else {
  571.                         last_special_line = abs(hang_after);
  572.                         if (hang_after < 0) {
  573.                                 first_width = hsize - abs(hang_indent);
  574.                                 first_indent = (hang_indent >= 0 ? hang_indent : 0);
  575.                                 second_width = hsize;
  576.                                 second_indent = 0;
  577.                         } else {
  578.                                 first_width = hsize;
  579.                                 first_indent = 0;
  580.                                 second_width = hsize - abs(hang_indent);
  581.                                 second_indent = (hang_indent >= 0 ? hang_indent : 0);
  582.                         }
  583.                 }
  584.         } else {
  585.                 last_special_line = info(par_shape_ptr) - 1;
  586.                 second_width = mem[par_shape_ptr + 2 * (last_special_line + 1)].sc;
  587.                 second_indent = mem[par_shape_ptr + 2 * last_special_line + 1].sc;
  588.         }
  589.         easy_line = (looseness == 0 ? last_special_line : MAX_HALFWORD);
  590.         threshold = pretolerance;
  591. #ifdef STAT
  592.         if (threshold >= 0) {
  593.                 if (tracing_paragraphs > 0) {
  594.                         begin_diagnostic();
  595.                         print_nl("@firstpass");
  596.                 } 
  597.                 second_pass = FALSE;
  598.         } else {
  599.                 threshold = tolerance;
  600.                 second_pass = TRUE;
  601.                 if (tracing_paragraphs > 0)
  602.                         begin_diagnostic();
  603.         }
  604. #else
  605.         if (threshold >= 0)
  606.                 second_pass = FALSE;
  607.         else {
  608.                 threshold = tolerance;
  609.                 second_pass = TRUE;
  610.         }
  611. #endif
  612.         loop {
  613.                 q = get_node(ACTIVE_NODE_SIZE);
  614.                 type(q) = UNHYPHENATED;
  615.                 fitness(q) = DECENT_FIT;
  616.                 link(q) = last_active;
  617.                 break_node(q) = NULL;
  618.                 line_number(q) = prev_graf + 1;
  619.                 total_demerits(q) = 0;
  620.                 link(active) = q;
  621.                 do_all_six(store_background);
  622.                 passive = NULL;
  623.                 printed_node = temp_head;
  624.                 pass_number = 0;
  625.                 font_in_short_display = NULL_FONT;
  626.                 cur_p = link(temp_head);
  627.                 auto_breaking = TRUE;
  628.                 prev_p = cur_p;
  629.                 while (cur_p != NULL && link(active) != last_active) {
  630.                         if (is_char_node(cur_p)) {
  631.                                 prev_p = cur_p;
  632.                                 do {
  633.                                         act_width += width_char(cur_p);
  634.                                         cur_p = link(cur_p);
  635.                                 } while (is_char_node(cur_p));
  636.                         }
  637.                         switch (type(cur_p))
  638.                         {
  639.                         case HLIST_NODE:
  640.                         case VLIST_NODE:
  641.                         case RULE_NODE:
  642.                                 act_width += width(cur_p);
  643.                                 break;
  644.                         
  645.                         case WHATSIT_NODE:
  646.                                 break;
  647.                         
  648.                         case GLUE_NODE:
  649.                                 if (auto_breaking) {
  650.                                         if (is_char_node(prev_p))
  651.                                                 try_break(0L, UNHYPHENATED);
  652.                                         else if (precedes_break(prev_p)) 
  653.                                                 try_break(0L, UNHYPHENATED);
  654.                                 }
  655.                                 check_shrinkage(glue_ptr(cur_p));
  656.                                 q = glue_ptr(cur_p);
  657.                                 act_width += width(q);
  658.                                 active_width[2 + stretch_order(q)] += stretch(q);
  659.                                 active_width[6] += shrink(q);
  660.                                 if (second_pass && auto_breaking) {
  661.                                         s = link(cur_p);
  662.                                         if (s != NULL) {
  663.                                                 loop {
  664.                                                         if (is_char_node(s)) {
  665.                                                                 c = qo(character(s));
  666.                                                                 hf = font(s);
  667.                                                         } else if (type(s) == LIGATURE_NODE) {
  668.                                                                 q = lig_ptr(s);
  669.                                                                 c = qo(character(q));
  670.                                                                 hf = font(q);
  671.                                                         } else if (type(s) == KERN_NODE &&
  672.                                                                         subtype(s) == NORMAL)
  673.                                                                 c = 128;
  674.                                                         else if (type(s) == WHATSIT_NODE)
  675.                                                                 c = 128;
  676.                                                         else goto done1;
  677.                                                         if (c < 128 && lc_code(c) != 0) {
  678.                                                                 if (lc_code(c) == c || uc_hyph > 0)
  679.                                                                         goto done2;
  680.                                                                 else goto done1;
  681.                                                         }
  682.                                                         s = link(s);
  683.                                                 }
  684.  
  685.                                         done2:
  686.                                                 hyf_char = hyphen_char[hf];
  687.                                                 if (hyf_char < 0 || hyf_char > 255)
  688.                                                         goto done1;
  689.                                                 ha = s;
  690.                                                 hn = 0;
  691.                                                 loop {
  692.                                                         if (is_char_node(s)) {
  693.                                                                 if (font(s) != hf)
  694.                                                                         goto done3;
  695.                                                                 c = qo(character(s));
  696.                                                                 if (c >= 128)
  697.                                                                         goto done3;
  698.                                                                 if (lc_code(c) == 0 || hn == 63)
  699.                                                                         goto done3;
  700.                                                                 hb = s;
  701.                                                                 incr(hn);
  702.                                                                 hu[hn] = c;
  703.                                                                 hc[hn] = lc_code(c) - 1;
  704.                                                         } else if (type(s) == LIGATURE_NODE) {
  705.                                                                 j = hn;
  706.                                                                 q = lig_ptr(s);
  707.                                                                 if (font(q) != hf)
  708.                                                                         goto done3;
  709.                                                                 do {
  710.                                                                         c = qo(character(q));
  711.                                                                         if (c >= 128)
  712.                                                                                 goto done3;
  713.                                                                         if (lc_code(c) == 0 || j == 63)
  714.                                                                                 goto done3;
  715.                                                                         incr(j);
  716.                                                                         hu[j] = c;
  717.                                                                         hc[j] = lc_code(c) - 1;
  718.                                                                         q = link(q);
  719.                                                                 } while (q != NULL);
  720.                                                                 hb = s;
  721.                                                                 hn = j;
  722.                                                         } else if (type(s) != KERN_NODE ||
  723.                                                                         subtype(s) != NORMAL)
  724.                                                                 goto done3;
  725.                                                         s = link(s);
  726.                                                 }
  727.  
  728.                                         done3:
  729.                                                 if (hn < 5)
  730.                                                         goto done1;
  731.                                                 loop {
  732.                                                         if (!is_char_node(s)) {
  733.                                                                 switch (type(s))
  734.                                                                 {
  735.                                                                 case LIGATURE_NODE:
  736.                                                                         break;
  737.  
  738.                                                                 case KERN_NODE:
  739.                                                                         if (subtype(s) != NORMAL)
  740.                                                                                 goto done4;
  741.                                                                         break;
  742.  
  743.                                                                 case WHATSIT_NODE:
  744.                                                                 case GLUE_NODE:
  745.                                                                 case PENALTY_NODE:
  746.                                                                 case INS_NODE:
  747.                                                                 case ADJUST_NODE:
  748.                                                                 case MARK_NODE:
  749.                                                                         goto done4;
  750.                                                                         break;
  751.                                                                 
  752.                                                                 default: 
  753.                                                                         goto done1;
  754.                                                                         break;
  755.                                                                 }
  756.                                                         }
  757.                                                         s = link(s);
  758.                                                 }
  759.  
  760.                                         done4:
  761.                                                 hyphenate();
  762.                                         }
  763.                                 }
  764.                                 done1:
  765.                                         break;
  766.                         
  767.                         case KERN_NODE:
  768.                                 kern_break();
  769.                                 break;
  770.                         
  771.                         case LIGATURE_NODE:
  772.                                 act_width += width_lig_char(cur_p);
  773.                                 break;
  774.                         
  775.                         case DISC_NODE:
  776.                                 s = pre_break(cur_p);
  777.                                 disc_width = 0;
  778.                                 if (s == NULL)
  779.                                         try_break(ex_hyphen_penalty, HYPHENATED);
  780.                                 else {
  781.                                         do {
  782.                                                 if (is_char_node(s))
  783.                                                         disc_width += width_char(s);
  784.                                                 else {
  785.                                                         switch (type(s))
  786.                                                         {
  787.                                                         case LIGATURE_NODE:
  788.                                                                 disc_width += width_lig_char(s);
  789.                                                                 break;
  790.                                                         
  791.                                                         case HLIST_NODE:
  792.                                                         case VLIST_NODE:
  793.                                                         case RULE_NODE:
  794.                                                         case KERN_NODE:
  795.                                                                 disc_width += width(s);
  796.                                                                 break;
  797.                                                         
  798.                                                         default:
  799.                                                                 confusion("disc3");
  800.                                                                 break;
  801.                                                         }
  802.                                                 }
  803.                                                 s = link(s);
  804.                                         } while (s != NULL);
  805.                                         act_width += disc_width;
  806.                                         try_break(hyphen_penalty, HYPHENATED);
  807.                                         act_width -= disc_width;
  808.                                 }
  809.                                 break;
  810.                         
  811.                         case MATH_NODE:
  812.                                 auto_breaking = (subtype(cur_p) == AFTER);
  813.                                 kern_break();
  814.                                 break;
  815.                         
  816.                         case PENALTY_NODE:
  817.                                 try_break(penalty(cur_p), UNHYPHENATED);
  818.                                 break;
  819.                         
  820.                         case MARK_NODE:
  821.                         case INS_NODE:
  822.                         case ADJUST_NODE:
  823.                                 break;
  824.                         
  825.                         default:
  826.                                 confusion("paragraph");
  827.                                 break;
  828.                         }
  829.                         prev_p = cur_p;
  830.                         cur_p = link(cur_p);
  831.                 }
  832.                 if (cur_p == NULL) {
  833.                         try_break(EJECT_PENALTY, HYPHENATED);
  834.                         if (link(active) != last_active) {
  835.                                 r = link(active);
  836.                                 fewest_demerits = AWFUL_BAD;
  837.                                 do {
  838.                                         if (type(r) != DELTA_NODE &&
  839.                                                 total_demerits(r) < fewest_demerits) {
  840.                                                 fewest_demerits = total_demerits(r);
  841.                                                 best_bet = r;
  842.                                         }
  843.                                         r = link(r);
  844.                                 } while (r != last_active);
  845.                                 best_line = line_number(best_bet);
  846.                                 if (looseness == 0)
  847.                                         goto done;
  848.                                 r = link(active);
  849.                                 actual_looseness = 0;
  850.                                 do {
  851.                                         if (type(r) != DELTA_NODE) {
  852.                                                 line_diff = (int) line_number(r) - (int) best_line;
  853.                                                 if (line_diff < actual_looseness &&
  854.                                                         looseness <= line_diff ||       
  855.                                                         line_diff > actual_looseness &&
  856.                                                         looseness >= line_diff) {
  857.                                                         best_bet = r;
  858.                                                         actual_looseness = line_diff;
  859.                                                         fewest_demerits = total_demerits(r);
  860.                                                 } else if (line_diff == actual_looseness &&     
  861.                                                         total_demerits(r) < fewest_demerits) {
  862.                                                         best_bet = r;
  863.                                                         fewest_demerits = total_demerits(r);
  864.                                                 }
  865.                                         }
  866.                                         r = link(r);
  867.                                 } while (r != last_active);
  868.                                 best_line = line_number(best_bet);
  869.                                 if (actual_looseness == looseness || second_pass)
  870.                                         goto done;
  871.                         }
  872.                 }
  873.                 for (q = link(active); q != last_active; q = cur_p) {
  874.                         cur_p = link(q);
  875.                         if (type(q) == DELTA_NODE)
  876.                                 free_node(q, DELTA_NODE_SIZE);
  877.                         else free_node(q, ACTIVE_NODE_SIZE);
  878.                 }
  879.                 for (q = passive; q != NULL; q = cur_p) {
  880.                         cur_p = link(q);
  881.                         free_node(q, PASSIVE_NODE_SIZE);
  882.                 }
  883. #ifdef STAT
  884.                 if (tracing_paragraphs > 0)
  885.                         print_nl("@secondpass"); 
  886. #endif
  887.                 threshold = tolerance;
  888.                 second_pass = TRUE;
  889.         }
  890.  
  891. done:
  892. #ifdef STAT
  893.         if (tracing_paragraphs > 0)
  894.                 end_diagnostic(TRUE);
  895.                 
  896. #endif
  897.         post_line_break(final_widow_penalty);
  898.         for (q = link(active); q != last_active; q = cur_p) {
  899.                 cur_p = link(q);
  900.                 if (type(q) == DELTA_NODE)
  901.                         free_node(q, DELTA_NODE_SIZE);
  902.                 else free_node(q, ACTIVE_NODE_SIZE);
  903.         }
  904.         for (q = passive; q != NULL; q = cur_p) {
  905.                 cur_p = link(q);
  906.                 free_node(q, PASSIVE_NODE_SIZE);
  907.         }
  908.         pack_begin_line = 0;
  909. }
  910.  
  911. post_line_break (final_widow_penalty)
  912.         val             final_widow_penalty;
  913. {
  914.         ptr             q;
  915.         ptr             r;
  916.         ptr             s;
  917.         int     t;
  918.         val             pen;
  919.         hword   cur_line;
  920.         scal    cur_width;
  921.         scal    cur_indent;
  922.         bool    disc_break;
  923.  
  924.         q = break_node(best_bet);
  925.         cur_p = NULL;
  926.         do {
  927.                 r = q;
  928.                 q = prev_break(q);
  929.                 next_break(r) = cur_p;
  930.                 cur_p = r;
  931.         } while (q != NULL);
  932.         cur_line = prev_graf + 1;
  933.         do {
  934.                 q = cur_break(cur_p);
  935.                 disc_break = FALSE;
  936.                 if (q != NULL) {
  937.                         if (type(q) == GLUE_NODE) {
  938.                                 delete_glue_ref(glue_ptr(q));
  939.                                 glue_ptr(q) = right_skip;
  940.                                 subtype(q) = RIGHT_SKIP_CODE + 1;
  941.                                 add_glue_ref(right_skip);
  942.                                 goto done;
  943.                         } else {
  944.                                 if (type(q) == DISC_NODE) {
  945.                                         t = replace_count(q);
  946.                                         if (t == 0)
  947.                                                 r = link(q);
  948.                                         else {
  949.                                                 r = q;
  950.                                                 while (t > 1) {
  951.                                                         r = link(r);
  952.                                                         decr(t);
  953.                                                 }
  954.                                                 s = link(r);
  955.                                                 if (!is_char_node(s) &&
  956.                                                         next_break(cur_p) != NULL &&
  957.                                                         cur_break(next_break(cur_p)) == s)
  958.                                                         s = r;
  959.                                                 r = link(s);
  960.                                                 link(s) = NULL;
  961.                                                 flush_node_list(link(q));
  962.                                                 replace_count(q) = 0;
  963.                                         }
  964.                                         if (post_break(q) != NULL) {
  965.                                                 s = post_break(q);
  966.                                                 while (link(s) != NULL)
  967.                                                         s = link(s);
  968.                                                 link(s) = r;
  969.                                                 r = post_break(q);
  970.                                                 post_break(q) = NULL;
  971.                                         }
  972.                                         if (pre_break(q) != NULL) {
  973.                                                 s = pre_break(q);
  974.                                                 link(q) = s;
  975.                                                 while (link(s) != NULL)
  976.                                                         s = link(s);
  977.                                                 pre_break(q) = NULL;
  978.                                                 q = s;
  979.                                         }
  980.                                         link(q) = r;
  981.                                         disc_break = TRUE;
  982.                                 } else/*DIFF*/
  983.                                 if (type(q) == MATH_NODE || type(q) == KERN_NODE)
  984.                                         width(q) = 0;
  985.                         }
  986.                 } else {
  987.                         q = temp_head; 
  988.                         while (link(q) != NULL)
  989.                                 q = link(q);
  990.                 }
  991.                 r = new_param_glue(RIGHT_SKIP_CODE);
  992.                 link(r) = link(q);
  993.                 link(q) = r;
  994.                 q = r;
  995.  
  996.         done:
  997.                 r = link(q);
  998.                 link(q) = NULL;
  999.                 q = link(temp_head);
  1000.                 link(temp_head) = r;
  1001.                 if (left_skip != zero_glue) {
  1002.                         r = new_param_glue(LEFT_SKIP_CODE);
  1003.                         link(r) = q;
  1004.                         q = r;
  1005.                 }
  1006.                 if (cur_line > last_special_line) {
  1007.                         cur_width = second_width;
  1008.                         cur_indent = second_indent;
  1009.                 } else if (par_shape_ptr == NULL) {
  1010.                         cur_width = first_width;
  1011.                         cur_indent = first_indent;
  1012.                 } else {
  1013.                         cur_width = mem[par_shape_ptr + 2 * cur_line].sc;
  1014.                         cur_indent = mem[par_shape_ptr + 2 * cur_line - 1].sc;
  1015.                 }
  1016.                 adjust_tail = adjust_head;
  1017.                 just_box = hpack(q, cur_width, EXACTLY);
  1018.                 shift_amount(just_box) = cur_indent;
  1019.                 append_to_vlist(just_box);
  1020.                 if (adjust_head != adjust_tail) {
  1021.                         link(tail) = link(adjust_head);
  1022.                         tail = adjust_tail;
  1023.                 }
  1024.                 adjust_tail = NULL;
  1025.                 if (cur_line + 1 != best_line) {
  1026.                         pen = inter_line_penalty;
  1027.                         if (cur_line == prev_graf + 1)
  1028.                                 pen += club_penalty;
  1029.                         if (cur_line + 2 == best_line)
  1030.                                 pen += final_widow_penalty;
  1031.                         if (disc_break)
  1032.                                 pen += broken_penalty;
  1033.                         if (pen != 0) {
  1034.                                 r = new_penalty(pen);
  1035.                                 link(tail) = r;
  1036.                                 tail = r;
  1037.                         }
  1038.                 }
  1039.                 incr(cur_line);
  1040.                 cur_p = next_break(cur_p);
  1041.                 if (cur_p != NULL) {
  1042.                         r = temp_head;
  1043.                         loop {
  1044.                                 q = link(r);
  1045.                                 if (q == cur_break(cur_p))
  1046.                                         break;
  1047.                                 if (is_char_node(q))
  1048.                                         break;
  1049.                                 if (non_discardable(q))
  1050.                                         break;
  1051.                                 if (subtype(q) == ACC_KERN && type(q) == KERN_NODE)
  1052.                                         break;
  1053.                                 r = q;
  1054.                         }
  1055.                         if (r != temp_head) {
  1056.                                 link(r) = NULL;
  1057.                                 flush_node_list(link(temp_head));
  1058.                                 link(temp_head) = q;
  1059.                         }
  1060.                 }
  1061.         } while (cur_p != NULL);
  1062.         if (cur_line != best_line || link(temp_head) != NULL)
  1063.                 confusion("line breaking");
  1064.         prev_graf = best_line - 1;
  1065. }
  1066.  
  1067. ptr
  1068. finite_shrink (p)
  1069.         ptr             p;
  1070. {
  1071.         ptr             q;
  1072.  
  1073.         if (no_shrink_error_yet) {
  1074.                 no_shrink_error_yet = FALSE;
  1075.                 print_err("Infinite glue shrinkage found in a paragraph");
  1076.                 help_shrink();
  1077.                 error();
  1078.         }
  1079.         q = new_spec(p);
  1080.         shrink_order(q) = NORMAL;
  1081.         delete_glue_ref(p);
  1082.         return q;
  1083. }
  1084.  
  1085. /*
  1086.  *      Help text
  1087.  */
  1088.  
  1089. help_shrink()
  1090. {
  1091.         help5("The paragraph just ended includes some glue that has",
  1092.         "infinite shrinkability, e.g., `\\hskip 0pt minus 1fil'.",
  1093.         "Such glue doesn't belong there---it allows a paragraph",
  1094.         "of any length to fit on one line. But it's safe to proceed,",
  1095.         "since the offensive shrinkability has been made finite.");
  1096. }
  1097.